package com.lcy.algorithm.huawei;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 题目描述
 *
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。
 *
 * 现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出层序遍历的结果。
 *
 * 输入描述
 *
 * 每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果。（每串只包含大写字母）
 *
 * 中间用单空格分隔。
 *
 * 输出描述
 *
 * 输出仅一行，表示层序遍历的结果，结尾换行。
 *
 * 用例
 * 输入	CBEFDA CBAEDF
 * 输出	ABDCEF
 * 说明
 *
 * 二叉树为：
 *
 *      A
 *     /   \
 *   B    D
 *  /      /  \
 * C    E   F
 */
public class 二叉树广度优先遍历 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String post = sc.next();
        String mid = sc.next();
        getResult(new Condition(post,mid));
    }

    /**
     * @param condition 后续。中序条件
     * @return 层序遍历结果
     */
    public static void getResult(Condition condition) {
        // 广度优先搜索的执行队列，先加入左子树，再加入右子树
        LinkedList<Condition> queue = new LinkedList<>();
        // 层序遍历出来的元素存放在ans中
        StringBuilder sb  = new StringBuilder();

        devideLR(condition, queue, sb);

        System.out.println(sb);
    }

    /**
     * 本方法用于从后序遍历、中序遍历序列中分离出：根，以及其左、右子树的后序、中序遍历序列
     *
     * @param condition 后续。中序条件
     * @param queue BFS的执行队列
     * @param sb
     */
    public static void devideLR(Condition condition,LinkedList<Condition> queue, StringBuilder sb) {
        // 后序遍历的最后一个元素就是根
        String post = condition.post;
        String mid = condition.mid;
        char rootEle = post.charAt(post.length() - 1);
        // 将根加入题解
        sb.append(rootEle);

        // 在中序遍历中找到根的位置rootIdx，那么该位置左边就是左子树，右边就是右子树
        int rootIdx = mid.indexOf(rootEle);

        // 左子树长度，左子树是中序遍历的0~rootIdx-1范围，长度为rootIdx
        int leftLen = rootIdx;

        // 如果存在左子树，即左子树长度大于0
        if (leftLen > 0) {
            // 则从后序遍历中，截取出左子树的后序遍历
            String leftPost = post.substring(0, leftLen);
            // 从中序遍历中，截取出左子树的中序遍历
            String leftMid = mid.substring(0, rootIdx);
            // 将左子树的后、中遍历序列加入执行队列
            queue.addLast(new Condition(leftPost, leftMid));
        }

        // 如果存在右子树，即右子树长度大于0
        if (post.length() - 1 - leftLen > 0) {
            // 则从后序遍历中，截取出右子树的后序遍历
            String rightPost = post.substring(leftLen, post.length() - 1);
            // 从中序遍历中，截取出右子树的中序遍历
            String rightMid = mid.substring(rootIdx + 1);
            // 将右子树的后、中遍历序列加入执行队列
            queue.addLast(new Condition(rightPost, rightMid));
        }

        while (queue.size() > 0) {
            Condition tmp = queue.removeFirst();
            devideLR(tmp, queue, sb);
        }
    }

    static class Condition{
        String post;
        String mid;
        public Condition(String post,String mid){
            this.post  = post;
            this.mid = mid;
        }
    }
}
